package com.zzw.hj44;

import java.util.*;

/**
 * @Project: hw_java
 * @Description: Sudoku
 * @Author: zzw
 */

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int[][] db = new int[10][10];//保存原始数据
            List<int[]> arr = new ArrayList<>();//记录0元素的位置
            for (int i = 1; i <= 9; i++) {
                for (int j = 1; j <= 9; j++) {
                    db[i][j] = in.nextInt();
                    if (db[i][j] == 0) {
                        arr.add(new int[]{i, j});
                    }
                }
            }

            dfs(arr, db);
            //打印
            for (int i = 1; i <= 9; i++) {
                for (int j = 1; j <= 9; j++) {
                    System.out.print(db[i][j] + " ");
                }
                System.out.println();
            }
        }
    }

    private static boolean dfs(List<int[]> arr, int[][] db) {
        for (int j = 0; j < arr.size(); j++) {
            int hang = arr.get(j)[0];
            int lie = arr.get(j)[1];
            //1-9去计算是否符合
            for (int i = 1; i <= 9; i++) {
                if (check(db, hang, lie, i)) {
                    db[hang][lie] = i;
                    List<int[]> temp = new ArrayList<>();
                    temp.addAll(arr);
                    temp.remove(j);
                    if (dfs(temp, db)) {
                        return true;
                    } else {
                        db[hang][lie] = 0;//回溯
                    }
                }
            }
            return false;
        }
        return true;
    }

    //行,列,3*3判断
    private static boolean check(int[][] db, int x, int y, int current) {
        for (int i = 1; i <= 9; i++) {
            //行
            if (db[x][i] == current) return false;
            //列
            if (db[i][y] == current) return false;
        }
        //3*3   1 4
        int hang = (x - 1) / 3 * 3 + 1; //3*3的起始行
        int lie = (y - 1) / 3 * 3 + 1; //3*3的起始列
        for (int i = hang; i < hang + 3; i++) {
            for (int j = lie; j < lie + 3; j++) {
                if (db[i][j] == current) {
                    return false;
                }
            }
        }
        return true;
    }

}